import java.util.Stack;

//栈的使用
class Solution {
    public String removeDuplicates1(String s) {
        Stack<Character> stack = new Stack<>();
        char[] str = s.toCharArray();
        for (int i = 0; i < str.length; i++) {
            if (!stack.isEmpty() && str[i] == stack.peek()) {
                stack.pop();
            } else {
                stack.push(str[i]);
            }
        }
        StringBuffer ret = new StringBuffer();
        while (!stack.isEmpty()) {
            ret.append(stack.pop());
        }
        ret.reverse();
        return ret.toString();
    }

    public String removeDuplicates(String s) {
        StringBuffer ret = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            if (ret.length() != 0 && ret.charAt(ret.length() - 1) == s.charAt(i)) {
                ret.deleteCharAt(ret.length() - 1);
            } else {
                ret.append(s.charAt(i));
            }
        }
        return ret.toString();
    }

    public boolean backspaceCompare(String s, String t) {
        StringBuffer str1 = new StringBuffer();
        StringBuffer str2 = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            if (str1.length() == 0 || s.charAt(i) != '#') {
                if (s.charAt(i) != '#') {
                    str1.append(s.charAt(i));
                }
            } else {
                str1.deleteCharAt(str1.length() - 1);
            }
        }
        for (int i = 0; i < t.length(); i++) {
            if (str2.length() == 0 || t.charAt(i) != '#') {
                if (t.charAt(i) != '#') {
                    str2.append(t.charAt(i));
                }
            } else {
                str2.deleteCharAt(str2.length() - 1);
            }
        }
        System.out.println(str1);
        System.out.println(str2);

        return str1.toString().equals(str2.toString());
    }

    // " 3+5 / 2 "
    public int calculate(String s) {
        char[] str = s.toCharArray();
        char ope = '+';
        Stack<Integer> stack = new Stack<>();
        int tmp = 0;
        for (int i = 0; i < str.length; i++) {
            if (str[i] == ' ') continue;
            if(str[i]<'0' || str[i] >'9') {
                ope = str[i];
            } else {
                int j = i;
                tmp = 0;
                while (j < s.length() && str[j] >= '0' && str[j] <= '9') {
                    tmp = tmp * 10 + (str[j] - '0');
                    j++;
                }
                i = j-1;

                if(ope == '+') {
                    stack.push(tmp);
                }else if(ope == '-') {
                    stack.push(-tmp);
                }else if(ope == '*') {
                    int x = stack.pop();
                    stack.push(x*tmp);
                }else if(ope == '/') {
                    int x = stack.pop();
                    stack.push(x/tmp);
                }
                ope = '0';
            }
        }
        int ret = 0;
        while(!stack.isEmpty()) {
            ret += stack.pop();
        }
        return ret;
    }
    //2[abc]3[cd]ef
    public String decodeString(String _s) {
        StringBuffer str = new StringBuffer();
        char[] s = _s.toCharArray();
        int i = 0,k =0;
        while(i<_s.length()) {
            if(s[i]>='0'&&s[i]<='9') {
                k = s[i] - '0';
            }else if(s[i] == '[') {
                int j = i;
                while(s[j]!=']') {
                    j++;
                }
                String tmp = _s.substring(i+1,j);
                i = j;
                while(k>0) {
                    str.append(tmp);
                    k--;
                }
            }else {
                int j = i;
                while(s[i]<'0' && s[i]>'9') {
                    j++;
                }
                String tmp = _s.substring(i,j);
                str.append(tmp);
            }
            i++;
        }

        return str.toString();
    }
}

public class Test {
    public static void main(String[] args) {
        String ret = new Solution().decodeString("3[a]2[bc]");
        System.out.println(ret);
    }
    public static void main2(String[] args) {
        int ret = new Solution().calculate("    99  ");
        System.out.println(ret);
    }
    public static void main1(String[] args) {
        boolean ret = new Solution().backspaceCompare("ab##", "c#d#");
        System.out.println(ret);

    }
}
